რა არის გრაფი. გრაფის წარმოდგენა
პროგრამაში; სიგანეში ძებნის ალგორითმი
(Breadth-First Search, BFS)
მარიამ გობრონიძე
გრაფის განსაზღვრება
გრაფი არაწრფივი მონაცემთა სტრუქტურაა, რომელიც შედგება წვეროების (vertices) და მათ
შორის დამაკავშირებელი წიბოებისაგან (edges). წვეროებს ზოგჯერ კვანძებსაც უწოდებენ.
📌 ფორმალური განსაზღვრება :
გრაფი წარმოდგენილია როგორც G(V, E), სადაც:
● V – წვეროების სიმრავლე
● E – წიბოების სიმრავლე
გრაფი და მისი წარმოდგენები
ორიენტირებული და არაორიენტირებული
გრაფები
გრაფის წიბო შეიძლება იყოს ორიენტირებული(directed) ან
არაორიენტირებული (undirected).
• (u,v) – წიბოზე იტყვიან რომ ორიენტირებულია u დან v-სკენ;
• მიუმართავ წიბოებს ხშირად {u,v} სიმრავლით არნიშნავენ;
გრაფი შეიძლება იყოს ორიენტირებული (directed),
არაორიენტირებული (undirected) ან შერეული (mixed).
ორიენტირებული გრაფი
თუ გრაფის ყველა წიბო ორიენტირებულია, გრაფს ეწოდება
ორიენტირებული გრაფი.
მაგალითი – ობიექტზე ორიენტირებული პროგრამა
• წვეროები = კლასები
• წიბოები = მემკვიდრეობა
• წიბოები არიან ორიენტირებულები , რადგან მემკვიდრეობა ასიმეტრიულია.
არაორიენტირებული გრაფები
თუ გრაფის არც ერთი წიბო არ არის ორიენტირებულია, გრაფს
ეწოდება არაორიენტირებული გრაფი.
მაგალითი – თანამშრომლობა
• კვლევითი თანამშრომლობის გამოსახვა შესაძლებელია გრაფის მეშვეობით.
• წვეროები — თითოეული წვერო წარმოადგენს მკვლევარს.
• წიბოები — წიბო აერთებს იმ მკვლევრებს, რომელთაც ერთად აქვთ
გამოქვეყნებული სტატია ან წიგნი.
შერეული გრაფი
თუ გრაფს გააჩნია ორიენტირებული წიბოები და
არაორიენტირებული წიბოები, ერთად, მაშინ ასეთ გრაფს უწოდებენ
შერეულ გრაფს.
მაგალითი – ქალაქის რუკა
წვეროები: გზაჯვარედინები ან ჩიხები
წიბოები: ქუჩის მონაკვეთები
● ორმხრივი ქუჩა – არაორიენტირებული წიბო
● ერთმხრივი ქუჩა – ორიენტირებული წიბო
გრაფის წარმოდგენის მეთოდები
გრაფის ორი ყველაზე გავრცელებული წარმოდგენის მეთოდია:
1. მოსაზღვრეობის მატრიცა (Adjacency Matrix)
2. მოსაზღვრეობის სია (Adjacency List)
(სიმარტივისათვის ჩვენ განვიხილავთ მხოლოდ შეუწონავ გრაფებს)
მოსაზღვრეობის მატრიცა
არსებობს სხვადასხვა სტრუქტურა გრაფების წარმოსადგენად
მოსაზღვრეობის მატრიცა არის n × n ზომის ორობითი (0-1) მატრიცა, სადაც:
● თუ i და j წვეროები დაკავშირებულია, მაშინ adjMat[i][j] = 1
● წინააღმდეგ შემთხვევაში, adjMat[i][j] = 0
არაორიენტირებული გრაფი და მისი წარმოდგენა
მოსაზღვრეობის მატრიცით
ორიენტირებული გრაფი და მისი წარმოდგენა
მოსაზღვრეობის მატრიცით
მატრიცის ყველა წევრის თავდაპირველი მნიშვნელობა განვსაზღვროთ, როგორც
0. ხოლო თუ a დან b ში გადის წიბო, ამ წვეროების შესაბამისი სვეტისა და
სტრიქონის თანაკვეთაზე ჩავწერთ 1-ს
მოსაზღვრეობის სია
უფრო ეფექტური გზაა მოსაზღვრეობის სიის გამოყენება :
მოსაზღვრეობის სია ინახავს თითოეული წვეროს მოსაზღვრე წვეროების სიას.
● adjList[i] – შეიცავს ყველა წვეროს, რომელიც დაკავშირებულია i წვეროსთან.
ქვემოთ მოცემულ არაორიენტირებულ გრაფს აქვს 3 წვერო. შესაბამისად,
შეიქმნება სიის მასივი ზომით 3, სადაც თითოეული ინდექსი წარმოადგენს
წვეროს.
წვეროს 0 - ორი მეზობელი ჰყავს (ანუ 1 და 2), ამიტომ მასივის 0-იან
ინდექსზე ჩაწერთ წვეროებს 1 და 2.
ანალოგიურად, წვეროს 1 ორი მეზობელი ჰყავს (ანუ 2 და 0), ამიტომ
მასივის 1-იან ინდექსზე ჩაწერთ წვეროებს 2 და 0.
ასევე, წვეროს 2 მეზობლები ჩასაწერი იქნება შესაბამის მასივში.
არაორიენტირებული გრაფის მოსაწღვრეობის
სიით წარმოდგენის მაგალითი
ქვემოთ მოცემულ ორიენტირებულ გრაფს აქვს 3 წვერო. შესაბამისად, შეიქმნება
სიის მასივი ზომით 3, სადაც თითოეული ინდექსი წარმოადგენს წვეროს.
წვეროს 0 - არ ჰყავს მეზობლები, ამიტომ მასივის 0-იან ინდექსზე სია ცარიელი
დარჩება.
წვეროს 1 - ორი მეზობელი ჰყავს (ანუ 0 და 2), ამიტომ მასივის 1-იან ინდექსზე
ჩაწერთ წვეროებს 0 და 2.
ანალოგიურად, წვეროს 2 მეზობლები ჩასაწერი იქნება შესაბამის მასივში.
ორიენტირებული გრაფიდ წარმოდგენა
მოსაზღვრეობის სიით
BFS
● BFS (სიგანეში ძიება) გრაფის ტრავერსირების ძირითადი ალგორითმია.
● იწყება მოცემული წვეროდან / კვანძიდან და ჯერ მეზობელ კვანძებს სტუმრობს.
● შემდეგ მათი მეზობლებს და ასე შემდეგ — ფენების მიხედვით.
● იყენებს queue მონაცემთა სტრუქტურას.
● განსხვავდება DFS-ისგან, რომელიც სიღრმეში მიდის.
მაგალითები
ალგორითმის აღწერა
ვამატებთ საწყის წვეროს რიგში (queue).
ვნიშნავთ როგორც მონახულებულს.
სანამ რიგი ცარიელი არაა:
● ვიღებთ ელემენტს რიგიდან.
● ვამატებთ შედეგებში.
● ვამატებთ მის მოუნახულებელ მეზობლებს რიგში.
დროითი სირთულე
O(V+E)
V – წვეროთა რაოდენობა
E – წიბოთა რაოდენობა
პრაქტიკული გამოყენებები
• სოციალური ქსელები
• ნავიგაცია და რუკები
• თამაშები და ბოტები
• ვირუსის გავრცელების სიმულაცია
• ცხრილების შედგენა
გმადლობთ ყურადღებისთვის!
